﻿using System;
using System.Text;

namespace ConsoleApplication1
{
	class NODE
	{
		public long id;
		public NODE left = null, right = null;

		public void walk_pre()
		{
			Console.Write("-{0}-", id);
			if (left != null) left.walk_pre();
			if (right != null) right.walk_pre();
		}

		public void walk_mid()
		{
			if (left != null) left.walk_mid();
			Console.Write("-{0}-", id);
			if (right != null) right.walk_mid();
		}

		public void walk_post()
		{
			if (left != null) left.walk_post();
			if (right != null) right.walk_post();
			Console.Write("-{0}-", id);
		}

		public enum DIRECTION { Left, Right }

		public NODE grow()
		{
			return grow(DIRECTION.Left).grow(DIRECTION.Right);
		}

		public NODE grow(DIRECTION dir)
		{
			switch (dir)
			{
				case DIRECTION.Left:
					if (left != null) break;
					left = new NODE { id = this.id * 10 };
					break;

				case DIRECTION.Right:
					if (right != null) break;
					right = new NODE { id = this.id * 10 + 1 };
					break;
			}
			return this;
		}

		public NODE grow(string path)
		{
			if (path == "") return this;

			string sub = path.Substring(1);
			switch (path[0])
			{
				case 'L':
					if (left == null)
						left = new NODE { id = id * 10 };

					left.grow(sub);
					break;

				case 'R':
					if (right == null)
						right = new NODE { id = id * 10 + 1 };

					right.grow(sub);
					break;
			}

			return this;
		}

		public NODE path2node(string path, StringBuilder exists)
		{
			NODE current;
			switch (path[0])
			{
				default:
					return null;

				case 'L':
					if (left == null) return null;
					current = left;
					break;

				case 'R':
					if (right == null) return null;
					current = right;
					break;
			}

			exists.Append(path[0]);

			if (path.Length == 1)
				return current;
			else
				return current.path2node(path.Substring(1), exists);
		}
	}

	class Program
	{
		static void Main(string[] _)
		{
			{
				var root = demo1();
				Console.Write("前序遍历：");
				root.walk_pre();
				Console.WriteLine();

				Console.Write("中序遍历：");
				root.walk_mid();
				Console.WriteLine();

				Console.Write("后序遍历：");
				root.walk_post();
				Console.WriteLine();

				StringBuilder longest = new StringBuilder();
				var found = root.path2node("LLR", longest);
				if (found == null) Console.WriteLine(found); else Console.WriteLine(found.id);
				Console.WriteLine(longest);
			}

			Console.WriteLine("===============================");

			{
				var root = demo2();
				Console.Write("前序遍历：");
				root.walk_pre();
				Console.WriteLine();

				Console.Write("中序遍历：");
				root.walk_mid();
				Console.WriteLine();

				Console.Write("后序遍历：");
				root.walk_post();
				Console.WriteLine();

				StringBuilder longest = new StringBuilder();
				var found = root.path2node("LLR", longest);
				if (found == null) Console.WriteLine(found); else Console.WriteLine(found.id);
				Console.WriteLine(longest);
			}

			Console.ReadKey();
		}

		static NODE demo1()
		{
			NODE root = new NODE { id = 5 };

			root.grow()
				.left.grow()
				.left.grow(NODE.DIRECTION.Right)
				.right.grow();

			root.right.grow(NODE.DIRECTION.Left)
				.left.grow(NODE.DIRECTION.Right);

			return root;
		}

		static NODE demo2()
		{
			return new NODE { id = 6 }.grow("LLRL")
									  .grow("LLRR")
									  .grow("LR")
									  .grow("RLR");
		}
	}
}